package codetop.microsoft.T42;

/**
 * @Author: 18362
 * @Create: 2022-08-15 20:59:19 星期一
 */
class Solution {
    public int trap(int[] height) {
        int[] left = new int[height.length], right = new int[height.length];
        int max = 0;
        for (int i=0; i<height.length; ++i) {
            left[i] = max;
            max = Math.max(max, height[i]);
        }
        max = 0;
        for (int i=height.length-1; i>=0; --i) {
            right[i] = max;
            max = Math.max(max, height[i]);
        }
        int sum = 0;
        for (int i=1; i<height.length-1; ++i) {
            int dif = Math.min(left[i], right[i]) - height[i];
            sum += Math.max(dif, 0);
        }
        return sum;
    }
}